package leetcode.interviewClassics;

import leetcode.Hot100.reverseList;
import leetcode.ListNode;

/**
 * @author Cheng Jun
 * Description: 编写一个函数，检查输入的链表是否是回文的。
 * https://leetcode-cn.com/problems/palindrome-linked-list-lcci/
 * @version 1.0
 * @date 2021/11/1 22:31
 */
public class isPalindrome {
    public static void main(String[] args) {
        ListNode listNode2 = new ListNode(1, null);
        ListNode listNode1 = new ListNode(2, listNode2);
        ListNode listNode0 = new ListNode(1, listNode1);
        System.out.println(isPalindrome(listNode0));
    }

    // 时间复杂度 O(n)，空间复杂度 O(1)
    // 链表与自身颠倒的链表比较
    static boolean isPalindrome(ListNode head) {
        ListNode reverse = reverse(head);
        while (reverse != null) {
            if (reverse.val != head.val) {
                return false;
            } else {
                reverse = reverse.next;
                head = head.next;
            }
        }
        return true;
    }

    /**
     * 反转链表
     * @author Cheng Jun
     * @date 2022/2/14 16:09
     * @param head
     * @return leetcode.ListNode
     * @see reverseList#reverseList2(leetcode.ListNode)
     */
    static ListNode reverse(ListNode head) {
        ListNode reverse = null;
        ListNode listNode = head;
        while (listNode != null) {
            ListNode temp = new ListNode(listNode.val);
            temp.next = reverse;
            reverse = temp;
            listNode = listNode.next;
        }
        return reverse;
    }
}
